19.4-1

$H$ $:=$ MAKE-HEAP()
INSERT($H$, $n$)
INSERT($H$, $n-1$)
INSERT($H$, $-\infty$)
EXTRACT-MIN($H$)

for $k$ from $n-2$ down to $1$:
  INSERT($H$, $k$)
  INSERT($H$, $\infty$)
  INSERT($H$, $-\infty$)
  EXTRACT-MIN($H$)
  DELETE($H$, $\infty$)

Loop Invariant:
In the start of each iteration, $H$ has one linear min-tree with $n-k$ elements, i.e. a chain with length $n-k$.

Initialization:
Before the for-loop starts, we have a Fibonacci heap $H$ consisting with one min-tree of 2 elements, i.e. a chain with length 2.

Maintenance:
Consider the EXTRACT-MIN operation in an iteration for some $k$, it will remove $-\infty$ and merge $H$ into one min-tree with almost linear shape but the root has two children. Then the DELETE operation make the min-tree to be linear and of $n-k+1$ elements.

Termination:
As above discussion, when the last iteration ends, $H$ has only one linear min-tree with $n-1+1=n$ elements

22.1-2

Adjacency-List:

$1 \mapsto 2 \to 3$
$2 \mapsto 1 \to 4 \to 5$
$3 \mapsto 1 \to 6 \to 7$
$4 \mapsto 2$
$5 \mapsto 2$
$6 \mapsto 3$
$7 \mapsto 3$

Adjacency-Matrix:

$\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}$

22.1-7

$(B B^T )_{ij}= \Sigma_{k=1}^{m}{B_{ik}B^{T}_{kj}} = \Sigma_{k=1}^{m}{B_{ik}B_{jk}}$ Note that, for given $k$, there are unique $i$ and $j$ of $1$ and $-1$ respectively.
Thus, for $i \neq j$, $$(B B^T )_{ij} = \Sigma_{k=1}^{m}{B_{ik}B_{jk}} = -(\text{# of edges connect vertices }i \text{ and } j)$$ And, for $i=j$, $$(B B^T )_{ij} = \Sigma_{k=1}^{m}{B_{ik}B_{ik}} = (\text{# of edges starts or ends in vertex }i)$$

22.2-1

22.2-8

Since if $u$ and $v$ are satisfying $\delta(u, v)$ equals to diameter of tree $T = (V, E)$, then both $u$ and $v$ are leaves, and there is only one path connecting $u$ and $v$. So we have the relation
$\text{diameter of } T = \max_{u, v \in V}{\delta(u, v)}$
$= \max_{v \in V}{ [(1^\text{st}\text{ highest height of }v\text{'s subtree}) + (2^\text{nd}\text{ highest height of }v\text{'s subtree})] }$

Design:

Current_Max $:=$ $0$
Tree-Diameter($T$):
  Evaluate-Height($T$, $T$.root)
  return Current_Max

Evaluate-Height($T$, $r$):
  if $r$ has no children, then return $0$

  let $H$ be new array, and its size equals to number of children of $r$
  for $v \in \{ \text{children of }r \}$
    $H[v] := $ Evaluate-Height($T$, $v$) $+$ $1$

  $h_1 := \max H$
  if $|H| > 1$:
    $ h_2 := \max (H - \{h_1\})$
  else:
    $h_2 := 0$

  if $h_1 + h_2 >$ Current_Max:
    Current_Max $:= h_1 + h_2$

  return $h_1$

Analysis:

The algorithm traveals entire tree, visits and allocates memory for storing height of each node once. $\implies$ The time complexity is $O(|V|)$.

Read 10.2,3,4

Done.